# -*- coding: utf-8 -*-
# @Author: bao
# @Date:   2017-01-21 10:40:23
# @Last Modified by:   bao
# @Last Modified time: 2017-02-20 21:37:49
#!/usr/bin/env python
# -*- coding: iso-8859-1 -*-
import logging
import struct
import copy
import time
import random
from datetime import datetime
from operator import attrgetter
from ryu.base import app_manager
from ryu.controller import ofp_event
from ryu.controller.handler import MAIN_DISPATCHER, DEAD_DISPATCHER
from ryu.controller.handler import CONFIG_DISPATCHER
from ryu.controller.handler import set_ev_cls
from ryu.ofproto import ofproto_v1_0
from ryu.ofproto import ether
from ryu.lib.packet import packet
from ryu.lib.packet import ethernet
from ryu.lib.packet import ipv4
from ryu.lib.packet import arp
from ryu.lib.ip     import ipv4_to_bin
from ryu.lib import addrconv
from ryu.lib import hub
from ryu.lib import ip
from ryu import cfg
import copy
import math
import ryu.networkx as nx

import demand_estimation as dm_est
import generate_topology as gen_topo

# User defined packet format
PREAMBLE = 'aa:aa:aa:aa:aa:aa'

TYPE_SET_NETWORK        = 0x8800
TYPE_GET_NETWORK        = 0x8811
TYPE_UPDATE_NETWORK     = 0x8822
TYPE_SET_FLOWTABLE      = 0x8833
TYPE_STATS_REQUEST      = 0x8844
TYPE_STATS_REPLY        = 0x8855
TYPE_CLEAR_FLOWTABLE    = 0x8866

# TYPE_GET_NETWORK pakcet definition
HEADER_SIZE     = 12
SWITCH_SIZE     = 8
HOST_SIZE       = 6

priority1 = 1
priority2 = 2

def convert_ip_to_int(ip):
    '''
    From string to int
    10.0.0.2 -> 167772162
    '''
    tmp = 0
    for b in ipv4_to_bin(ip):
        tmp |= ord(b)
        tmp = tmp << 8
    tmp = tmp >> 8
    return tmp

class ClassName(object):
    """docstring for ClassName"""
    def __init__(self, arg):
        super(ClassName, self).__init__()
        self.arg = arg
        
class Detour_Controller(app_manager.RyuApp):
    OFP_VERSIONS = [ofproto_v1_0.OFP_VERSION]
    _NAME = 'detour_controller'

    def __init__(self, *args, **kwargs):
        super(Detour_Controller, self).__init__(*args, **kwargs)
        self.name = "detour_controller"

        CONF = cfg.CONF
        CONF.register_opts([
        cfg.IntOpt('links', default=0),
        cfg.IntOpt('static_links', default=1),
        cfg.FloatOpt('interval', default=0.05),
        cfg.IntOpt('threshold', default=100000000),
        cfg.FloatOpt('switching_time', default=0.001),
        cfg.BoolOpt('reconfigure', default=False),
        cfg.StrOpt('con_type', default="Detour")])

        self.logger.info("links:%d"% CONF.links)
        self.logger.info("static_links:%d"% CONF.static_links)
        self.logger.info("interval:%f"% CONF.interval)
        self.logger.info("threshold:%d"% CONF.threshold )
        self.logger.info("switching_time:%f"% CONF.switching_time)
        self.logger.info("reconfigure:%s"% CONF.reconfigure)
        self.logger.info("con_type:%s"% CONF.con_type)
        
        self.links          = CONF.links
        self.static_links   = CONF.static_links     # The static graph, which links are no reconfigurable, from port 1:static_links
        self.interval       = CONF.interval         # Periodicity get the traffic matrix (Seconds)
        self.threshold      = CONF.threshold        # Flow Throughput threshold (bps)
        self.switching_time = CONF.switching_time   # Circuit switching time (Seconds)
        self.reconfigure    = CONF.reconfigure      # Enable the reconfigure
        self.con_type       = CONF.con_type

        '''
        edge attributes: 'port': [port1,...,portN] one edge has multi-port means that has higher bandwidth, defalut the first port, aggraget the bandwidth
        node attributes: 'host': [(port,host_ip),...,(port,host_ip)]
        port num [1:k]
        '''
        self.dps = {}           # datapath_id => Datapath class
        self.access_table = {}  # {(dpid,port)->host_ip}
        self.host_location = {} # {host_ip:(dpid,port)}
        self.en_network         = "com_network" #
        self.com_network        = nx.DiGraph()  # Including all the information of the network, host and switch
        self.mid_network        = nx.DiGraph()  # The overlap between the dynamic netowrk
        self.static_network     = nx.DiGraph()  # Reserve a static, connected channel in the network
        self.dynamic_network    = nx.DiGraph()  # Network constructed by dynamic links
        self.com_routes         = {}            # Com_network routing entries {datapath_id:{dst_ip, outports}}
        self.mid_routes         = {}            # Mid_network routing entries

        # flow demand estimation
        self.counter    = 1
        self.switches   = []
        self.flows_src  = {}    # {'converged': False, 'demand': througput, 'recLimited': False}
        self.flows_dst  = {}    # {'converged': False, 'demand': througput, 'recLimited': Fvalse}
        self.recon_enable = False
        self.static_counter = 0
        self.in_configure = False
        
        self.discover_thread = hub.spawn(self._discover)

    def _discover(self):
        '''
        The main thread.
        '''
        self.logger.info("Initial the network")

        time.sleep(4) # Wait for the connections between switches and controller
        self.Initial()

        time.sleep(4) # Get the traffic demand matrix
        if self.reconfigure:
            self.logger.info("--------------------------round %s--------------------------" %self.counter)
            self.stats_request(int(self.interval*1000), self.threshold)

        while self.reconfigure:
            if self.recon_enable:
                self.counter += 1
                self.recon_enable = False
                if self.in_configure == True:
                    self.in_configure = False
                if len(self.flows_src)!=0 or len(self.flows_dst)!=0:
                    self.reconfigure_network()
                else:
                    self.static_counter += 1
                    if self.static_counter <= 3:
                        self.reconfigure_network()
                    
                self.switches = self.dps.keys()
                self.flows_src = {}
                self.flows_dst = {}
            time.sleep(0.0000001)

    @set_ev_cls(ofp_event.EventOFPSwitchFeatures, CONFIG_DISPATCHER)
    def switch_features_handler(self, ev):
        datapath = ev.msg.datapath
        self.dps[datapath.id] = datapath
        self.com_routes[datapath.id] = {}
        self.mid_routes[datapath.id] = {}
        self.logger.info("switch:%s connected", datapath.id)

    def Initial(self):
        '''
        Get the topology
        '''
        self.set_network()
        time.sleep(0.0001)
        self.get_network()
        time.sleep(0.0001)

        self.dynamic_links = self.links-self.static_links
        self.sub_copy(self.static_network, self.com_network, self.dynamic_links+1, self.links)
        self.sub_copy(self.dynamic_network, self.com_network, 1, self.dynamic_links)
        
        self.show_topology(self.com_network)
        self.show_topology(self.static_network, True, True, False)
        self.show_topology(self.dynamic_network, True, True, False)
        # Get the basic parameter of the topology
        self.switches   = self.dps.keys()
        self.switches_num = len(self.dps.keys())
        self.bp_src = list(self.com_network.nodes())
        self.bp_dst = [x+self.switches_num for x in self.bp_src]
        self.row_size = int(math.ceil(math.sqrt(self.switches_num)))

        self.pre_matches = self.bp_matches(self.dynamic_network, self.dynamic_links, self.switches_num)
        for x in xrange(1,len(self.pre_matches)+1):
            self.logger.info(self.pre_matches[x])
        
        self.set_flowtable(1,1,0) # enable the mid_flowtable
        time.sleep(0.0000001)
        self.install_last_hop_flows(self.com_network, priority1)
        self.set_flowtable(0,0,0)
        time.sleep(0.0000001)
        self.install_last_hop_flows(self.com_network, priority1)

    def set_network(self):
        '''
        Initial the neighbours of the data plane
        Frame Format:
        6 MAC ADDR :'aa:aa:aa:aa:aa:aa'
        2 Type : TYPE_SET_NETWORK
        '''
        self.logger.info("set_network")
        pkt_data = bytearray(8)
        struct.pack_into("!6sH", pkt_data, 0, addrconv.mac.text_to_bin(PREAMBLE), TYPE_SET_NETWORK)

        for dp in self.dps.itervalues():
            actions = [dp.ofproto_parser.OFPActionOutput(dp.ofproto.OFPP_CONTROLLER)]
            dp.send_packet_out(actions=actions, data=pkt_data)
    
    def get_network(self):
        '''
        Get the topology of the data plane
        Frame Format
        6 MAC ADDR :'aa:aa:aa:aa:aa:aa'
        2 Type : TYPE_GET_NETWORK
        '''
        self.logger.info("get_network")
        pkt_data = bytearray(8)
        struct.pack_into("!6sH", pkt_data, 0, addrconv.mac.text_to_bin(PREAMBLE), TYPE_GET_NETWORK)

        for dp in self.dps.itervalues():
            actions = [dp.ofproto_parser.OFPActionOutput(dp.ofproto.OFPP_CONTROLLER)]
            dp.send_packet_out(actions=actions, data=pkt_data)

    def get_link2port(self, graph, src_dpid, dst_dpid):
        if (src_dpid, dst_dpid) in list(graph.edges()):
            return graph.edge[src_dpid][dst_dpid]['port']
        else:
            self.logger.debug("Link to port is not found.")
            return None

    def get_host_location(self, host_ip):
        if host_ip in self.host_location:
            return self.host_location[host_ip]
        else:
            self.logger.debug("%s location is not found." % host_ip)
            return None

    def get_demand(self, filename):
        with open(filename, 'r') as f:
            for line in f.readlines():
                self.logger.info("%s" %line)

    def sub_copy(self, sub_graph, graph, cutoff_l = 0, cutoff_h = 0):
        '''
        copy the graph that the attributes "port" attributes of each edge is in [cutoff_l, cutoff_h]
        cutoff_l = cutoff_h means copy all the graph.
        '''
        for sw_src in list(graph.nodes()):
            sub_graph.add_node(sw_src, host = graph.node[sw_src]['host'])
            for sw_dst in list(graph.nodes()):
                if (sw_src, sw_dst) in list(graph.edges()):
                    port_list = []
                    ports = graph.edge[sw_src][sw_dst]['port']
                    for port in ports:
                        if port >= cutoff_l and port <= cutoff_h:
                            port_list.append(port)
                    if port_list:
                        sub_graph.add_edge(sw_src, sw_dst, port=port_list)

    def stats_request(self, delay=100, threshold=10):
        '''
        # Frame Format
        # 6 MAC ADDR :'aa:aa:aa:aa:aa:aa'
        # 2 Type : TYPE_STATS_REQUEST
        # 4 Delay: Milliseconds
        # 4 Threshold: Mbps
        '''
        self.logger.info("stats_request at time %s" %datetime.now())

        pkt_data = bytearray(16)
        struct.pack_into("!6sHII", pkt_data, 0, addrconv.mac.text_to_bin(PREAMBLE), TYPE_STATS_REQUEST, delay, threshold)

        for dp in self.dps.itervalues():
            actions = [dp.ofproto_parser.OFPActionOutput(dp.ofproto.OFPP_CONTROLLER)]
            dp.send_packet_out(actions=actions, data=pkt_data)

    def reconfigure_network(self):
        '''
        @ 1.demand estimation
        @ 2.generate topology
        @ 3.wavelength assignment
        @ 4.reconfigure network
        '''
        self.logger.info("reconfigure_network at time %s" %datetime.now())
        
        tf_graph = nx.Graph()
        fully_wl_graph = nx.Graph()
        ovs_wl_graph = nx.Graph()
        
        for src in self.bp_src:
            tf_graph.add_node(src, bipartite=0, forward=0, degree=0)
            fully_wl_graph.add_node(src, bipartite=0, forward=0, degree=0)
            ovs_wl_graph.add_node(src, bipartite=0, forward=0, degree=0)
        for dst in self.bp_dst:
            tf_graph.add_node(dst, bipartite=1, forward=0, degree=0)
            fully_wl_graph.add_node(dst, bipartite=1, forward=0, degree=0)
            ovs_wl_graph.add_node(dst, bipartite=1, forward=0, degree=0)
        
        # 1. demand estimation max-min fariness
        Host_Matrix = dm_est.demand_estimation(self.flows_src, self.flows_dst)
        dm_est.transform (Host_Matrix, self.host_location, tf_graph, self.switches_num)

        
        if self.con_type == "Detour":
            self.logger.info("Detour")
            gen_topo._transform_fully(fully_wl_graph, tf_graph, self.dynamic_links, self.switches_num)
            max_degree_fully = gen_topo._augment_regular_fully(fully_wl_graph, self.dynamic_links, self.switches_num)
            cur_matches_fully = gen_topo._matchings(fully_wl_graph, self.pre_matches, max_degree_fully, self.switches_num)
            (d_matches, s_matches, new_matches) = gen_topo._color_assignment(self.pre_matches, cur_matches_fully, self.switches_num)
        elif self.con_type == "OvS":
            self.logger.info("OvS")
            gen_topo._transform_ovs(ovs_wl_graph, tf_graph, self.dynamic_links, self.row_size, self.switches_num)
            max_degree_ovs = gen_topo._augment_regular_ovs(ovs_wl_graph, self.dynamic_links, self.row_size, self.switches_num)
            cur_matchings_ovs = gen_topo._matchings(ovs_wl_graph, self.pre_matches, max_degree_ovs, self.switches_num)
            (d_matches, s_matches, new_matches) = gen_topo._color_assignment(self.pre_matches, cur_matchings_ovs, self.switches_num)
        else:
            self.logger.info("!!!!!")

        if False:
            for src in fully_wl_graph.nodes():
                dsts_dic = fully_wl_graph.neighbors(src)
                dsts = list(dsts_dic)
                self.logger.info("%s %s %s" %(src, dsts, fully_wl_graph.node[src]['degree']))
                for dst in dsts:
                    self.logger.info("(%s,%s),%s" %(src,dst,fully_wl_graph.edge[src][dst]['weight']))

        if True:
            for k in new_matches:
                self.logger.info("new_matches %s %s" %(k, len(new_matches[k])))
                self.logger.info("%s" %sorted(new_matches[k]))
            
            for k in s_matches:
                self.logger.info("s_matches %s %s" %(k, len(s_matches[k])))
                self.logger.info("%s" %sorted(s_matches[k]))
            
            for k in d_matches:
                self.logger.info("d_matches %s %s" %(k, len(d_matches[k])))
                self.logger.info("%s" %sorted(d_matches[k]))
        '''
        2.Update the network topology and routing
        @ d_matches: update the network of the data plane
        @ s_matches: update the mid_network, combine with the static_network(which guarantees the network is connected)
        @ new_matches: update the com_network of the control plane
        '''
        d_matches_empty = 0
        for k in d_matches:
            d_matches_empty |= len(d_matches[k])
            if d_matches_empty:
                break
        if d_matches_empty:
            self.pre_matches = copy.deepcopy(new_matches)
            self.com_network = self.static_network.copy()
            self.mid_network = self.static_network.copy()
            self.logger.info("mid_network")
            self.update_ct_network(self.mid_network, s_matches)
            self.logger.info("com_network")
            self.update_ct_network(self.com_network, new_matches)
            self.show_topology(self.com_network, True, True, False)
            
            self.set_flowtable(1,1,0) #enable the mid_flowtable
            self.en_network = "mid_network"
            self.logger.info("mid_network")
            self.update_k_routes(self.mid_network, self.mid_routes)

            if self.in_configure ==True:
                time.sleep(0.00000001)
            else:
                time.sleep(self.switching_time)
            
            self.update_dt_network(self.com_network, d_matches)
            
            self.set_flowtable(0,0,0) #enable the com_flowtable
            self.logger.info("com_network")
            self.en_network = "com_network"
            #self.update_k_routes(self.com_network, self.com_routes)
        self.logger.info("--------------------------round %s--------------------------" %self.counter)
        self.stats_request(int(self.interval*1000), self.threshold)

    def update_ct_network(self, graph, matches):
        '''
        update the network topology in the controller based on the new matches
        '''
        for port in matches:
            for match_tuple in matches[port]:
                if (match_tuple[0], match_tuple[1]-self.switches_num) not in list(graph.edges()):
                    graph.add_edge(match_tuple[0], match_tuple[1]-self.switches_num, port=[port])
                elif port not in graph[match_tuple[0]][match_tuple[1]-self.switches_num]['port']:
                    graph[match_tuple[0]][match_tuple[1]-self.switches_num]['port'].append(port)
                    ports = graph[match_tuple[0]][match_tuple[1]-self.switches_num]['port']
                    graph[match_tuple[0]][match_tuple[1]-self.switches_num]['port']=sorted(ports)

        if True:
            for src in graph.nodes():
                dsts_dic = graph.neighbors(src)
                dsts = list(dsts_dic)
                self.logger.info("%s %s" %(src, dsts))
                for dst in dsts:
                    self.logger.info("(%s,%s),%s" %(src,dst,graph.edge[src][dst]['port']))
    
    def update_dt_network(self, graph, d_matches):
        '''
        update the network topology in the data plane based on the new dynamical matches
        @ d_matches: Update the network of the data plane

        Frame Format
        6 MAC ADDR :'aa:aa:aa:aa:aa:aa'
        2 Type : TYPE_UPDATE_TOPOLOGY
        2 circuit num : n
        2 rate num : m adjust the device's daterate
        4 <src_portNum 1(2), dst_datapathID(2)> 1
          ....
        4 <src_portNum n(2), dst_datapathID(2)> n
        4 <src_portNum 1(2), daterate> 
          ....
        4 <src_portNum m(2), daterate> 
        '''
        self.logger.info("update_network at time %s" %datetime.now())
        matches = {} # {src:{port:dst}}
        rates = {} # {src:{port:rate}}
        for src in list(graph.nodes()):
            rates[src]={}
            matches[src]={}
            dsts= graph.neighbors(src)
            for dst in dsts:
                if len(graph.edge[src][dst]['port'])>1:
                    first_port = graph.edge[src][dst]['port'][0]
                    rates[src][first_port] = len(graph.edge[src][dst]['port'])
        self.logger.info("rates")
        self.logger.info(rates)

        for port in d_matches:
            for match_tuple in d_matches[port]:
                if match_tuple[0] in matches:
                    matches[match_tuple[0]][port] = match_tuple[1]-self.switches_num
                else:
                    matches[match_tuple[0]] = {}
                    matches[match_tuple[0]][port] = match_tuple[1]-self.switches_num
        self.logger.info("matches")
        self.logger.info(matches)
        
        # adjust the network
        for datapath in self.dps.itervalues():
            size = 12 + 4*len(matches[datapath.id]) + 4*len(rates[datapath.id])
            pkt_data = bytearray(size)
            struct.pack_into("!6sHHH", pkt_data, 0, addrconv.mac.text_to_bin(PREAMBLE), TYPE_UPDATE_NETWORK, len(matches[datapath.id]), len(rates[datapath.id]))
            counter = 0
            for port in matches[datapath.id]:
                dst_datapathID = matches[datapath.id][port]
                struct.pack_into("!HH", pkt_data, 12+counter*4, port, dst_datapathID)
                counter += 1
            counter = 0
            for port in rates[datapath.id]:
                daterate = rates[datapath.id][port]
                struct.pack_into("!HH", pkt_data, 12+counter*4+len(matches[datapath.id])*4, port, daterate)
                counter += 1

            actions = [datapath.ofproto_parser.OFPActionOutput(datapath.ofproto.OFPP_CONTROLLER)]
            datapath.send_packet_out(actions=actions, data=pkt_data)
    
    def update_routes(self, graph, routes, dst_mask=16):
        '''
        Update the data plane routes as the network changed
        '''
        self.logger.info("update_shortest_routes at time %s" %datetime.now())
        for src_sw in routes:
            for dst_sw in routes[src_sw]:
                path = nx.shortest_path(graph, src_sw, dst_sw)
                outPort = self.get_link2port(graph, path[0], path[1])

                self.logger.info("[%s,%s] outPort:%s new_outport:%s" %(src_sw,dst_sw,routes[src_sw][dst_sw],[outPort[0]]))

                if routes[src_sw][dst_sw] != [outPort[0]]:
                    self.logger.info("Modify the routes")
                    routes[src_sw][dst_sw] = [outPort[0]]

                    datapath = self.dps[src_sw]
                    ofproto = datapath.ofproto
                    parser = datapath.ofproto_parser

                    actions = []
                    actions = [parser.OFPActionOutput(outPort[0])]

                    dst_ip = self.access_table[(dst_sw, self.links+1)]
                    match = parser.OFPMatch(
                            nw_dst = convert_ip_to_int(dst_ip),
                            nw_dst_mask = dst_mask)

                    self.flow_mod(datapath, priority1, match, ofproto.OFPFC_MODIFY,
                        actions, 0, 0)

    def update_k_routes(self, graph, routes, dst_mask=16):
        '''
        Update the data plane routes as the network changed
        '''
        self.logger.info("update_k_shortest_routes at time %s" %datetime.now())
        for src_sw in routes:
            for dst_sw in routes[src_sw]:
                self.logger.info("%s-->%s: outPorts:%s"%(src_sw, dst_sw, routes[src_sw][dst_sw]))

        for src_sw in routes:
            
            datapath = self.dps[src_sw]
            ofproto = datapath.ofproto
            parser = datapath.ofproto_parser

            for dst_sw in routes[src_sw]:
                pathes = []
                tmp_cutoff = 1
                while not pathes:
                    pathes = list(nx.all_simple_paths(graph, src_sw, dst_sw, tmp_cutoff))
                    tmp_cutoff += 1
                if len(pathes)>4:
                    pathes = pathes[0:3]

                actions = []
                outPorts = []
                if len(pathes[0]) > 2: # multi-hop and multi-pathes                    
                    for path in pathes:
                        outPort = self.get_link2port(graph, path[0], path[1])
                        outPorts.append(outPort[0])
                        actions.append(parser.OFPActionOutput(outPort[0])) # default first outport

                    self.logger.info("[%s,%s] outPorts:%s new_outPorts:%s" %(src_sw,dst_sw,routes[src_sw][dst_sw],outPorts))
                    
                    if routes[src_sw][dst_sw] != outPorts:
                        self.logger.info("Modify the routes")
                        routes[src_sw][dst_sw] = outPorts
                        
                        dst_ip = self.access_table[(dst_sw, self.links+1)]
                        match = parser.OFPMatch(
                                nw_dst = convert_ip_to_int(dst_ip),
                                nw_dst_mask = dst_mask)

                        self.flow_mod(datapath, priority1, match, ofproto.OFPFC_MODIFY,
                            actions, 0, 0)
                    else:
                        self.logger.info("route exists")

                elif len(pathes[0]) > 1: # two sws: one hop
                    path = pathes[0]
                    outPort = self.get_link2port(graph, path[0], path[1])
                    outPorts = outPort[0]

                    self.logger.info("[%s,%s] outPorts:%s new_outPorts:%s" %(src_sw,dst_sw,routes[src_sw][dst_sw],[outPorts]))

                    if routes[src_sw][dst_sw] != [outPorts]:
                        self.logger.info("Modify the routes")
                        routes[src_sw][dst_sw] = [outPorts]

                        actions = [parser.OFPActionOutput(outPort[0])]

                        dst_ip = self.access_table[(dst_sw, self.links+1)]
                        match = parser.OFPMatch(
                                nw_dst = convert_ip_to_int(dst_ip),
                                nw_dst_mask = dst_mask)

                        self.flow_mod(datapath, priority1, match, ofproto.OFPFC_MODIFY,
                            actions, 0, 0)
                    else:
                        self.logger.info("route exists")

    def bp_matches(self, DiGraph, degree, switch_nums):
        '''
        Calculate k matches
        '''
        self.logger.info("bp_matches at time %s" %datetime.now())
        # 1.Transform the graph to bipartite graph
        bp_graph = nx.Graph()
        bp_graph.add_nodes_from(self.bp_src, bipartite=0)
        bp_graph.add_nodes_from(self.bp_dst, bipartite=1)

        for edge in list(DiGraph.edges()):
            bp_graph.add_edge(edge[0], edge[1]+switch_nums)
                
        # 2.Decompose the graph to k matches
        match_results = {} # port_num: matching
        for x in range (1, degree+1):
            match = nx.bipartite.maximum_matching(bp_graph)
            temp_match = []
            for src,dst in match.items():
                if src > switch_nums:
                    break       
                temp_match.append((src,dst))
                bp_graph.remove_edge(src,dst)
            match_results[x] = temp_match
        return match_results

    def install_last_hop_flows(self, graph, priority=priority1):
        self.logger.info("install_last_hop_flows")
        for sw in list(graph.nodes()):
            datapath = self.dps[sw]
            ofproto = datapath.ofproto
            parser = datapath.ofproto_parser

            for host in graph.node[sw]['host']:
                outport = host[0]
                nw_dst = host[1]
                self.logger.info("outport:%s ---> host_ip: %s" %(outport, nw_dst))
                actions = [parser.OFPActionOutput(outport)]
                match = parser.OFPMatch(
                    nw_dst = convert_ip_to_int(nw_dst))

                self.flow_mod(datapath, priority, match, ofproto.OFPFC_ADD, actions)
    
    def flow_mod(self, datapath, p, match, command, actions, idle_timeout=0, hard_timeout=0):
        ofproto = datapath.ofproto
        parser = datapath.ofproto_parser

        mod = parser.OFPFlowMod(
            datapath=datapath, match=match, cookie=0,
            command=command, idle_timeout=idle_timeout, hard_timeout=hard_timeout,
            priority=p,
            flags=ofproto.OFPFF_SEND_FLOW_REM, actions=actions)
        
        datapath.send_msg(mod)

    def install_flow(self, path, dst_ip, dst_sw, routes, dst_mask=16):
        '''
        @path=[dpid1, dpid2, dpid3...]
        @dst_ip
        @dst_sw
        @routes
        '''
        # first flow entry
        assert path
        self.logger.info("dst_ip:%s" %dst_ip)
        # inter_link
        if len(path) > 2:
            self.logger.info("path > 2")
            for i in xrange(0, len(path)-1):
                port = self.get_link2port(self.com_network, path[i], path[i+1])
                self.logger.info("(%s,%s) outport:%s" %(path[i],path[i+1],port[0]))
                
                datapath = self.dps[path[i]]
                ofproto = datapath.ofproto
                parser = datapath.ofproto_parser

                actions = []
                actions = [parser.OFPActionOutput(port[0])]

                match = parser.OFPMatch(
                        nw_dst = convert_ip_to_int(dst_ip),
                        nw_dst_mask = dst_mask)

                #1. routes not exists
                if dst_sw not in routes[path[i]]:
                    self.logger.info("add new flow")
                    routes[path[i]][dst_sw] = [port[0]]
                    self.flow_mod(datapath, priority1, match, ofproto.OFPFC_ADD,
                        actions, 0, 0)
                elif routes[path[i]][dst_sw] != [port[0]]:
                    self.logger.info("modify flow")
                    routes[path[i]][dst_sw] = [port[0]]
                    self.flow_mod(datapath, priority1, match, ofproto.OFPFC_MODIFY,
                        actions, 0, 0)
                else:
                    self.logger.info("flow exists")

        elif len(path) > 1:
            self.logger.info("path > 1")
            # the  first flow entry
            port = self.get_link2port(self.com_network, path[0], path[1])
            self.logger.info("(%s,%s) outport:%s" %(path[0],path[1],port[0]))

            datapath = self.dps[path[0]]
            ofproto = datapath.ofproto
            parser = datapath.ofproto_parser

            actions = []
            actions = [parser.OFPActionOutput(port[0])]
            
            match = parser.OFPMatch(
                    nw_dst = convert_ip_to_int(dst_ip),
                    nw_dst_mask = dst_mask)
            
            if dst_sw not in routes[path[0]]:
                self.logger.info("add new flow")
                routes[path[0]][dst_sw] = [port[0]]
                self.flow_mod(datapath, priority1, match, ofproto.OFPFC_ADD,
                    actions, 0, 0)
            elif routes[path[0]][dst_sw] != [port[0]]:
                self.logger.info("modify flow")
                routes[path[0]][dst_sw] = [port[0]]
                self.flow_mod(datapath, priority1, match, ofproto.OFPFC_MODIFY,
                    actions, 0, 0)
            else:
                self.logger.info("flow exists")

        else:  # src and dst on the same
            self.logger.info("path ==0!!!!")

    def install_flows(self, graph, pathes, dst_ip, dst_sw, routes, dst_mask=16):
        '''
        @pathes = [[dpid1, dpid2,...,dpidn],[dpid1, dpid3,...,dpidn],...,[dpid1, dpidk,...,dpidn]]
        @dst_ip
        @dst_sw
        @routes
        '''
        # first flow entry
        assert pathes
        
        self.logger.info("pathes %s" %pathes)
        if len(pathes[0]) > 2: # multi-hop and multi-pathes
            '''
            Filter the pathes, the next_sw may be same in diff pathes
            Such as [[1, 11, 7, 10], [1, 11, 9, 10], [1, 12, 9, 10]]
            '''
            last_sw = pathes[0][-1]
            next_swtiches = {}
            for path in pathes:
                for sw in path:
                    if sw != last_sw:
                        if sw not in next_swtiches:
                            next_swtiches[sw] = [path[path.index(sw)+1]]
                        else:
                            if path[path.index(sw)+1] not in next_swtiches[sw]:
                                next_swtiches[sw].append(path[path.index(sw)+1])
            self.logger.info(next_swtiches)

            for src_sw in next_swtiches:                
                datapath = self.dps[src_sw]
                ofproto = datapath.ofproto
                parser = datapath.ofproto_parser

                actions = []
                outPorts = []
                next_sws = next_swtiches[src_sw]
                for next_sw in next_sws:
                    outPort = self.get_link2port(graph, src_sw, next_sw)
                    outPorts.append(outPort[0])
                    actions.append(parser.OFPActionOutput(outPort[0])) # default first outport

                self.logger.info("%s-->%s: outPorts:%s"%(src_sw, dst_sw, outPorts))
                
                match = parser.OFPMatch(
                        nw_dst = convert_ip_to_int(dst_ip),
                        nw_dst_mask = dst_mask)

                if dst_sw not in routes[src_sw]:
                    self.logger.info("add new flow")
                    routes[src_sw][dst_sw] = outPorts
                    self.flow_mod(datapath, priority1, match, ofproto.OFPFC_ADD,
                        actions, 0, 0)
                elif routes[src_sw][dst_sw] != outPorts:
                    self.logger.info("modify flow")
                    routes[src_sw][dst_sw] = outPorts
                    self.flow_mod(datapath, priority1, match, ofproto.OFPFC_MODIFY,
                        actions, 0, 0)
                else:
                    self.logger.info("flow exists")

        elif len(pathes[0]) > 1: # two sws: one hop
            # dynamical link bandwidth. aggregate outports, default the first outport
            self.logger.info("path > 1")
            outPort = self.get_link2port(graph, pathes[0][0], pathes[0][1])
            self.logger.info("(%s,%s) outport:%s" %(pathes[0][0],pathes[0][1], outPort[0]))

            datapath = self.dps[pathes[0][0]]
            ofproto = datapath.ofproto
            parser = datapath.ofproto_parser

            actions = []
            actions = [parser.OFPActionOutput(outPort[0])]
            
            match = parser.OFPMatch(
                    nw_dst = convert_ip_to_int(dst_ip),
                    nw_dst_mask = dst_mask)
            
            src_sw = pathes[0][0]
            if dst_sw not in routes[src_sw]:
                self.logger.info("add new flow")
                routes[src_sw][dst_sw] = [outPort[0]]
                self.flow_mod(datapath, priority1, match, ofproto.OFPFC_ADD,
                    actions, 0, 0)
            elif routes[src_sw][dst_sw] != [outPort[0]]:
                self.logger.info("modify flow")
                routes[src_sw][dst_sw] = [outPort[0]]
                self.flow_mod(datapath, priority1, match, ofproto.OFPFC_MODIFY,
                    actions, 0, 0)
            else:
                self.logger.info("flow exists")

        else:  # src and dst on the same
            self.logger.info("path ==0!!!!")
        
    def set_flowtable(self, wFlowTable=0, rFlowTable=0, clearTable=0):
        '''
        Set the flowtable
        Frame Format
        6 MAC ADDR :'aa:aa:aa:aa:aa:aa'
        2 Type : TYPE_SET_FLOWTABLE
        1 m_wFlowTable : 0:m_comFlowTable 1:m_midFlowTable
        1 m_rFlowTable : 0:m_comFlowTable 1:m_midFlowTable
        1 m_clearTable : 0 not clear, 1 clear m_comFlowTable, 2 clear m_midFlowTable
        '''
        self.logger.info("set_flowtable %s" %datetime.now())

        pkt_data = bytearray(11)
        struct.pack_into("!6sHBBB", pkt_data, 0, addrconv.mac.text_to_bin(PREAMBLE), TYPE_SET_FLOWTABLE, wFlowTable, rFlowTable, clearTable)

        for dp in self.dps.itervalues():
            actions = [dp.ofproto_parser.OFPActionOutput(dp.ofproto.OFPP_CONTROLLER)]
            dp.send_packet_out(actions=actions, data=pkt_data)
    
    @set_ev_cls(ofp_event.EventOFPPacketIn, MAIN_DISPATCHER)
    def _packet_in_handler(self, ev):
        msg = ev.msg
        datapath = msg.datapath
        ofproto = datapath.ofproto
        parser = datapath.ofproto_parser

        in_port = msg.in_port
        pkt = packet.Packet(msg.data)

        preamble_bin, pkt_type = struct.unpack_from("!6sH", pkt.data)
        preamble = addrconv.mac.bin_to_text(preamble_bin)
        
        if preamble == PREAMBLE: # user defined packet
            if pkt_type == TYPE_GET_NETWORK:
                '''
                Frame Format
                6 MAC ADDR :'aa:aa:aa:aa:aa:aa'
                2 Type : TYPE_GET_NETWORK
                2 switch link num : m
                2 host link num : n
                8 <src_portNum, dst_portNum, dst_datapathID> 1
                  ....
                8 <src_portNum, dst_portNum, dst_datapathID> m
                6 <src_portNum, Ipv4Address> 1
                  ....
                6 <src_portNum, Ipv4Address> n
                '''
                self.logger.info("TYPE_GET_NETWORK %s" %datapath.id)
                (switch_link_num, host_link_num) = struct.unpack_from("!HH", pkt.data, 8)
                self.logger.info((switch_link_num, host_link_num))
                
                for x in xrange(0,switch_link_num):
                    (src_portNum, dst_portNum, dst_datapathID) = struct.unpack_from("!HHI", pkt.data, HEADER_SIZE+x*SWITCH_SIZE)
                    self.logger.info((src_portNum, dst_portNum, dst_datapathID))
                    
                    if (datapath.id, dst_datapathID) not in list(self.com_network.edges()):
                        self.com_network.add_edge(datapath.id, dst_datapathID, port = [src_portNum])
                    elif src_portNum not in self.com_network[datapath.id][dst_datapathID]['port']:
                        self.com_network[datapath.id][dst_datapathID]['port'].append(src_portNum)
                        ports = self.com_network[datapath.id][dst_datapathID]['port']
                        self.com_network[datapath.id][dst_datapathID]['port'] = sorted(ports)

                    if host_link_num == 0 and datapath.id not in self.core_sw:
                        self.core_sw.append(datapath.id)

                host_list = []
                for x in xrange(0,host_link_num):
                    (src_portNum, host_ip) = struct.unpack_from("!H4s", pkt.data, HEADER_SIZE+switch_link_num*SWITCH_SIZE+x*HOST_SIZE)
                    self.logger.info((src_portNum, ip.ipv4_to_str(host_ip)))
                    self.access_table[(datapath.id, src_portNum)] = ip.ipv4_to_str(host_ip)
                    self.host_location[ip.ipv4_to_str(host_ip)] = (datapath.id, src_portNum)
                    host_list.append((src_portNum,ip.ipv4_to_str(host_ip)))
                self.com_network.add_node(datapath.id, host=host_list)

            if pkt_type == TYPE_STATS_REPLY:
                '''
                Frame Format
                6 MAC ADDR :'aa:aa:aa:aa:aa:aa'
                2 Type : TYPE_STATS_REPLY
                4 Flow nums:
                10 Flow ID:<in_port(2), destIP(4), througput(4)>
                '''
                self.logger.info("sw:%s stats_reply time:%s" %(datapath.id,datetime.now()))
                
                (flows_num,) = struct.unpack_from("!I", pkt.data, 8)
                for x in xrange(0,flows_num):
                    (in_port, dst_ip_int, througput) = struct.unpack_from("!HII", pkt.data, 12+x*10)
                    self.logger.info((datapath.id,in_port))
                    src_ip = self.access_table[(datapath.id,in_port)]
                    dst_ip = ip.ipv4_to_str(dst_ip_int)

                    if src_ip not in self.flows_src:
                        self.flows_src[src_ip]={}
                    if dst_ip not in self.flows_dst:
                        self.flows_dst[dst_ip]={}
                    
                    self.flows_src[src_ip][dst_ip] = {'converged': False, 'demand': througput, 'recLimited': False}
                    self.flows_dst[dst_ip][src_ip] = {'converged': False, 'demand': througput, 'recLimited': False}
                    self.logger.info("%s %s %s %s" %(in_port, src_ip, dst_ip, througput))

                self.switches.remove(datapath.id)
                # collect all of the swithes' traffic
                if not self.switches:
                    self.recon_enable = True
                    
        else: # normal ethernet packet
            self.logger.info("switch:%s" %datapath.id)
            dst_mac, src_mac, eth_type = struct.unpack_from("!6s6sH", pkt.data)
            ip_pkt = pkt.get_protocol(ipv4.ipv4)

            if isinstance(ip_pkt, ipv4.ipv4):
                src_ip = ip_pkt.src
                dst_ip = ip_pkt.dst
                dst_location = self.get_host_location(dst_ip)
                dst_sw, dst_out_port = dst_location[0], dst_location[1]
                
                # Firstly, install new rule (k-shortest path routing)
                outport = 0
                tmp_cutoff = 1
                path = []
                pathes = []
                
                if self.en_network == "com_network":
                    while not pathes :
                        pathes = list(nx.all_simple_paths(self.com_network, datapath.id, dst_sw, tmp_cutoff))
                        tmp_cutoff += 1
                    if len(pathes)>4:
                        pathes = pathes[0:3]

                    path = random.choice(pathes)
                    outport = self.get_link2port(self.com_network, path[0], path[1])
                    self.logger.info( "Com_network PATH[%s --> %s]:%s %s" % (src_ip, dst_ip, pathes, path))

                    #self.install_flow(path, dst_ip, dst_sw, self.com_routes)
                    self.install_flows(self.com_network, pathes, dst_ip, dst_sw, self.com_routes)
                else:
                    while not pathes:
                        pathes = list(nx.all_simple_paths(self.mid_network, source=datapath.id, target=dst_sw, cutoff=tmp_cutoff))
                        tmp_cutoff += 1
                    if len(pathes)>4:
                        pathes = pathes[0:3]

                    path = random.choice(pathes)
                    outport = self.get_link2port(self.mid_network, path[0], path[1])
                    self.logger.info( "Mid_network PATH[%s --> %s]:%s %s" % (src_ip, dst_ip, pathes, path))

                    #self.install_flow(path, dst_ip, dst_sw, self.mid_routes)
                    self.install_flows(self.mid_network, pathes, dst_ip, dst_sw, self.mid_routes)

                # Secondly, send the packet out
                actions = []
                actions = [parser.OFPActionOutput(outport[0])]
                
                msg_data = None
                if msg.buffer_id == ofproto.OFP_NO_BUFFER:
                    msg_data = msg.data

                out = parser.OFPPacketOut(
                    datapath=datapath, buffer_id=msg.buffer_id,
                    data=msg_data, in_port=in_port, actions=actions)

                datapath.send_msg(out)

    def show_topology(self, graph, topo = True, link = True, host = True):
        #directed k regular graph, egress and ingress degree are equal and all nodes' degree are equal
        switch_num = len(graph)
        if topo:
            print "---------------------Topo Link---------------------"
            print '%4s' % ("switch"),
            for sw in list(graph.nodes()):
                print '%3d' % sw,
            print ""
            
            for sw_src in list(graph.nodes()):
                print '%6d' % sw_src,
                for sw_dst in list(graph.nodes()):
                    if sw_src == sw_dst:
                        print '%3s' % "0",
                    elif (sw_src, sw_dst) in list(graph.edges()):
                        if graph.edge[sw_src][sw_dst]['port']:
                            print '%3s' % "1",
                        else:
                            print '%3s' % "*",
                    else:
                        print '%3s' % "*",
                print ""

        # show link
        if link:
            print "---------------------Link Port---------------------"
            print '%2s' % ("switch"),
            for sw in list(graph.nodes()):
                print '%4d' % sw,
            print ""
            for sw_src in list(graph.nodes()):
                print '%6d' % sw_src,
                for sw_dst in list(graph.nodes()):
                    if (sw_src, sw_dst) in list(graph.edges()):
                        if graph.edge[sw_src][sw_dst]['port']:
                            print '%s' % "[",
                            for port in graph.edge[sw_src][sw_dst]['port']:
                                print '%s' % str(port), #if has multi port, only show the first port
                            print '%s' % "]",
                        else:
                            print '%3s' % "[]",
                    else:
                        print '%3s' % "[]",
                print ""

        # show host
        if host:
            print "----------------Access Host-------------------"
            print '%10s' % ("switch"), '%12s' % "Host"

            for sw in list(graph.nodes()):
                for host in graph.node[sw]['host']:
                    print '%10d:    ' % sw, host[1]
